1
Principi della Minimizzazione Senza Vincoli
MATH008Lesson 9
00:00
Passiamo dall'esistenza teorica di un minimo all'architettura algoritmica dell'ottimizzazione. Il nostro obiettivo principale è minimizzare $f(x)$ (9.1) dove $f: \mathbf{R}^n \to \mathbf{R}$ è convessa e due volte continuamente differenziabile. Poiché $f$ è differenziabile e convessa, una condizione necessaria e sufficiente affinché un punto $x^*$ sia ottimale è $\nabla f(x^*) = 0$.

Il Quadro Algoritmico

Le soluzioni numeriche costruiscono una sequenza di minimizzazione: Una sequenza di punti $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$ con $f(x^{(k)}) \to p^*$ quando $k \to \infty$. Ogni passo aggiorna la posizione tramite $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$, dove $\Delta x$ è una direzione di discesa.

Inizializzazione e Convergenza

I metodi descritti in questo capitolo richiedono un punto di partenza adatto $x^{(0)}$. Il punto di partenza deve trovarsi in $\text{dom } f$, e inoltre l'insieme dei livello inferiore $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ deve essere chiuso. Ciò garantisce che la sequenza rimanga in una regione ben comportata dove l'Hessiana fornisce informazioni utili.

Direzioni di Discesa

La direzione più semplice è $\Delta x = -\nabla f(x)$. Tuttavia, l'efficienza spesso richiede di tener conto di diverse geometrie attraverso la direzione di discesa più ripida:

  • Norma Quadratica: $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$.
  • $L_\infty$ Norma: $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ (Discesa per coordinate).

Modelli del Secondo Ordine e Regioni di Fiducia

Il metodo di Newton utilizza un'approssimazione di Taylor del secondo ordine: $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ Questa funzione quadratica è minimizzata quando $v = \Delta x_{nt}$ (passo di Newton). Definiamo una regione di fiducia: l'insieme $\{v \mid \|v\|_2 \le \gamma\}$. Il parametro $\gamma$ riflette la nostra fiducia nel modello del secondo ordine. Quando il modello è accurato, risolviamo la direzione tramite $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ nei sistemi KKT.

🎯 Principi Fondamentali della Convergenza
L'efficienza viene misurata dalla velocità con cui l'errore $f(x^{(k)}) - p^*$ tende a zero. Per funzioni fortemente convesse, l'errore $f(x^{(k)}) - p^*$ converge a zero almeno così rapidamente come una serie geometrica. Nel contesto dei metodi numerici iterativi, ciò si chiama convergenza lineare.
  • Bound di Subottimalità: $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$, valido se $\lambda(x) < 1$.
  • Somma di Self-Concordanza: Se $f_1, f_2$ sono self-concordanti, allora $f_1 + f_2$ è self-concordante.
  • Sparsità dell'Hessiana: L'efficienza aumenta se la condizione di struttura a banda dell'Hessiana: $\nabla^2 f(x)_{ij} = 0$ per $|i-j| > k$ è soddisfatta.